/**
 * 
 */
package base.algorithm.dfa;

import java.io.UnsupportedEncodingException;
import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.List;


/**
 * @author Administrator
 *
 */
public class DFA {
	 /**  
	  * ��ڵ�  
	   */  
	  private TreeNode rootNode = new TreeNode();   
	     
	  /**  
	   * �ؼ�ʻ���  
	   */  
	  private ByteBuffer keywordBuffer = ByteBuffer.allocate(1024);      
	     
	  /**  
	   * �ؼ�ʱ���  
	   */  
	  private String charset = "GBK";   

	  /**  
	   * ����DFA  
	   * @param keywordList  
	   * @throws UnsupportedEncodingException   
	   */  
	  public void createKeywordTree(List<String> keywordList) throws UnsupportedEncodingException{   
	      for (String keyword : keywordList) {   
	          if(keyword == null) continue;   
	          keyword = keyword.trim();   
	          byte[] bytes = keyword.getBytes(charset);   
	             
	          TreeNode tempNode = rootNode;   
	          //ѭ��ÿ���ֽ�   
	          for (int i = 0; i < bytes.length; i++) {   
	              int index = bytes[i] & 0xff; //�ַ�ת��������   
	              TreeNode node = tempNode.getSubNode(index);   
	                 
	              if(node == null){ //û��ʼ��   
	                   node = new TreeNode();   
	                   tempNode.setSubNode(index, node);   
	               }   
	                  
	               tempNode = node;   
	                  
	               if(i == bytes.length - 1){   
	                   tempNode.setKeywordEnd(true);    //�ؼ�ʽ��� ���ý����־   
	                  // logger.debug("DFA:{}", keyword);   
	               }   
	           }//end for   
	       }//end for     
	   }   
	      
	   /**  
	    * �����ؼ���  
	    */  
	   public String searchKeyword(String text) throws UnsupportedEncodingException{   
	       return searchKeyword(text.getBytes(charset));   
	   }   
	      
	   /**  
	    * �����ؼ���  
	    */  
	   public String searchKeyword(byte[] bytes){   
	       StringBuilder words = new StringBuilder();   
	          
	       if(bytes == null || bytes.length == 0){   
	           return words.toString();   
	       }   
	          
	       TreeNode tempNode = rootNode;   
	       int rollback = 0;   //�ع���   
	       int position = 0; //��ǰ�Ƚϵ�λ��   
	          
	       while (position < bytes.length) {   
	           int index = bytes[position] & 0xFF;   
	           keywordBuffer.put(bytes[position]); //д�ؼ�ʻ���   
	           tempNode = tempNode.getSubNode(index);   
	              
	           //��ǰλ�õ�ƥ�����   
	           if(tempNode == null){    
	               position = position - rollback; //���� ��������һ���ֽ�   
	               rollback = 0;   
	               tempNode = rootNode;    //״̬��λ   
	               keywordBuffer.clear();  //���   
	           }   
	           else if(tempNode.isKeywordEnd()){  //�ǽ���� ��¼�ؼ��   
	               keywordBuffer.flip();   
	               String keyword = Charset.forName(charset).decode(keywordBuffer).toString();   
	              // logger.debug("Find keyword:{}", keyword);   
	               System.out.println("Find keyword:"+keyword);  
	               keywordBuffer.limit(keywordBuffer.capacity());   
	                  
	               if( words.length() == 0 ) words.append(keyword);   
	               else words.append(":").append(keyword);   
	                  
	               rollback = 1;   //���������  rollback ��Ϊ1   
	            }else{     
	                rollback++; //�ǽ���� �������1   
	            }   
	               
	            position++;   
	        }   
	           
	        return words.toString();   
	    }   
	       
	    public void setCharset(String charset) {   
	        this.charset = charset;   
	    }   

	    public static void main(String []fs){
	    	DFA dfa =new DFA();
	    	List <String> keywordList=new ArrayList<String>();
	    	keywordList.add("��å");
	    	keywordList.add("����");
	    	keywordList.add("С��");
	    	keywordList.add("������");
	    	keywordList.add("������,�����å,������");
	    	keywordList.add("����������,");
	    	keywordList.add("�����");
	    	try {
				dfa.createKeywordTree(keywordList);
				dfa.searchKeyword("����������,�����å,������С��");
			} catch (UnsupportedEncodingException e) {
				System.err.println(e);
			}
			
	    }

}
